1. Field of the Invention
The invention relates to the art of color image processing. For example, it finds application where an image created on, or prepared for rendering on, a first or source device is prepared for rendering on a second or destination device.
2. Description of Related Art
When an image is prepared for rendering on an electronic device the image is represented as a set of pixels. Each pixel describes a small portion of the image in terms of colorant pixel values for the colorants available on the rendering device. For example, typically a cathode ray tube (CRT) based computer display screen is comprised of red (R), green (G) and blue (B) phosphors. An image prepared for display on a CRT is described with a set of pixels. Each pixel describes the intensity with which the red, green and blue phosphors are to be illuminated on a small portion of the CRT. A similar procedure is followed when an image is prepared for rendering on a printing device. Currently, at least some color printing devices apply cyan (C), magenta (M), yellow (Y), and sometimes black (K) colorants to a print medium, such as paper or velum, in order to render an image. Such printing devices are said to operate in a CMY or CMYK color space. When an image is prepared for rendering on a color-printing device, the image is represented as a set of pixels. Each pixel describes a small portion of the image by calling for an appropriate mixture of the available colorants. Typically, the pixel value for each colorant can range from 0 to 255. The higher a colorant""s pixel value is, the more of that colorant the color image processor applies to the print medium. In a system employing 8-bit precision for the colorant signals, the number 255 represents the maximum or fully saturated amount of colorant. The number 0 is used when none of a particular colorant is required.
In a CRT operating in RGB (red, green blue) space, fully saturated red is described by a pixel calling for R=255, G=0, B=0. In a printer operating in CMYK (cyan, magenta, yellow, black) space, fully saturated red is described by a pixel calling for C=0, M=255, Y=255, K=0 Magenta and yellow colorants combine through simple subtractive mixing and are perceived as red. There is no guarantee that the red described in RGB space and displayed on the CRT is the same red described in CMYK space and printed on a page. In fact, it is quite likely that the spectral properties of the red phosphor used in the CRT will be different than the spectral properties of the subtractively mixed magenta and yellow colorants of a particular printer.
As mentioned above, the CRT and the CMYK printer use different materials to generate the perception of color. The materials used impact the set of colors that each device can reproduce.
The set of colors a device can produce is referred to as the color gamut of the device. There is no guarantee that a color that can be produced by a first device is within the color gamut of a second device. This is even true when both devices are CMYK printers.
Where color matching is required between two devices such as the CRT operating in RGB space and the printer operating in CMYK space, transforms based on calibration and measurement are required. In such a situation it is possible, for example, that the pure red RGB CRT pixel mentioned above, is mapped to a CMYK printer pixel calling for a less than fully saturated magenta component and a small amount of a cyan component. For example, the CMYK version of the original RGB red pixel referred to above might call for C=27, M=247, Y=255, K=0. Furthermore, if one wants to print a copy of the original pure red RGB CRT pixel on a second printer it is quite likely that a second transform will have to be used. That transform may translate the original RGB CRT pixel to a second CMYK pixel. For example, the second transform may map the original RGB CRT pixel to a second CMYK pixel calling for C=20, M=234, Y=240, K=35. One reason two different CMYK printers may require different transforms is that different printers use different colorants. For example, a first magenta colorant used in a first printer may have a different spectral content than a second magenta colorant used in a second printer. Likewise, a first yellow colorant used in a first printer may have a different spectral content than a second yellow colorant used in a second printer.
From the foregoing discussion it can be seen that an image prepared for rendering on a first device may need to be transformed if it is to be properly rendered on a second device. Such a transformation is an attempt to emulate the first or source device onto the second or destination device. In order to achieve calorimetric matching, the emulation of the color gamut of the CRT on the first CMYK printer caused the red CRT pixel to be mapped to a first CMYK pixel calling for C=27, M=247, Y=255, K=0. The emulation of the color gamut of the CRT on the second CMYK printer caused the red CRT pixel to be mapped to the second CMYK pixel calling for C=20, M=234, Y=240, K=35. Obviously, therefore, even where there is no RGB CRT image involved, an image prepared for printing on the first printer may have to be transformed before its calorimetric content can be matched on the second printer. In such a situation the first printer is said to be emulated on the second printer.
For example, when, a photographic image has been prepared for rendering on a first CMYK device, for example a Standard Web Offset Printing (SWOP) device, but must then be rendered on a second CMYK device, for example, a xerographic printer, a xe2x80x9c4 to 4xe2x80x9d transform is typically used to emulate the first device on the second device.
An image processor must be able to satisfactorily transform images, prepared for rendering on a staggeringly large number of source devices, for rendering on an equally large number of rendering devices. For example, a personal computer, configured to operate as an image processor, through the use of, for example, a web browser, word processor, or desktop publishing software, must be able to accept images created or downloaded from almost anywhere, and render the images pleasingly on any image output terminal the user connects to the personal computer. For example, the image processor must be able to pleasingly display images on a computer screen and send commands to have images rendered pleasingly on any printer the user connects to the personal computer. Similarly, document processors and copiers must transform images pleasingly and accurately. Indeed, in document processors and copiers, color accuracy requirements can be very stringent. For example, in a large print job, comprising a corporate sales presentation, it is very important that colors in a company logo be reproduced accurately and consistently. Similarly, colors in a clothing catalog must match the colors on depicted garments.
Typically transformations are carried using look up tables. For example, an image prepared for rendering in a RGB color space of a computer monitor, is transformed into a CMYK color space of a printer, using a three-dimensional look up table. Each of the RGB parameters is used as an axis or index into the look up table. The RGB parameters are typically represented by 8-bit values for each of the R, G, and B components. Such a 24-bit RGB vector is capable of addressing over 16.77 million locations or describing over 16.77 million colors. However, look up tables of this size are physically impractical in most cases. Therefore, such look up tables are typically partitioned into a smaller size, such as, for example, 16xc3x9716xc3x9716 (4096) table locations or nodes. Each node stores, for example, a CMYK value. CMYK values of points not directly represented by nodes, are determined by a form of interpolation among nodes of the look up table (LUT).
An illustration of the operation of a prior art look up table is instructive. Referring to FIG. 1, an input RGB value is used to determine index values r, g, b into the table 112. The index values are used to locate the transformation data within the table. For example, the index values corresponding to a point 116 do not coincide with any node location 120. Therefore, a transformation value is not directly available from the table 112. Instead, the conversion is accomplished by interpolating between the CMYK values stored in nodes 124 corresponding to the point 116. For example, the nodes 124 correspond to the point 116 because they are the nodes 124 nearest the input point 116. The input RGB color is defined in three dimensions. Therefore, the interpolation is done in three dimensions. Common examples of 3-D interpolation techniques include trilinear, tetrahedral, and prism interpolation. Of these, tetrahedral interpolation is the fastest method, requiring interpolation only among 4 nodes. (The trilinear and prism schemes utilize 8 and 6 nodes, respectively.) All these techniques require several multiplication, addition, shift, and comparison operations for each output signal or parameter at each pixel; and are often implemented with special purpose hardware. This interpolated CMYK value is then output. Typically, the output is eventually rendered, for example, on a printer.
A look-up table suitable for color transformations is a tiling of a portion of color space corresponding at least to the color gamut of the intended (real or virtual) input device. (A tiling of space is a division of space into abutting regions with no voids)
As depicted in FIG. 1, tiling in prior art look up tables is even and regular. That is to say, each tile is a cube, and the dimensions of each cube are the same. For example, each cube or tile is four parameter value increments wide, four parameter value increments high, and four parameter value increments deep. Such a look up table includes 26,144 tiles or cubes arranged in a grid of 64xc3x9764xc3x9764 cubes or tiles. In other words, every fourth parameter value is represented by a node. For example, a red axis has a nodes at R=0, 3, 7, 11 . . . 251, 255. Likewise a green axis has nodes at G=0, 3, 7, 11 . . . 251, 255. and a blue axis has nodes at B=0, 3, 7, 11 . . . 251, 255. Those skilled in the art will recognize that determining which cube, tile, or nodes to use, in a prior art look up table, to determine a transformation value for a set of RGB parameter values is a trivial matter. For example, where the pixel parameter values are represented by eight bit words, an appropriate tile, is found by shifting the bits in the eight bit words. For example, R greater than  greater than 2, G greater than  greater than 2, B greater than  greater than 2 shifts bits representing an RGB parameter value, two positions to the right, leaving the six highest order bits in each parameter for use as an index or address of the appropriate node. The two low order bits of the three values indicate the position corresponding to the input color description within the cube or tile. The low order bits are used in interpolating between the nodes of the cube or tile.
This indexing and tile accessing method is very fast. However, the speed comes at a price. In order to use this prior art indexing method, one is forced to quantize or tile a color space into equal, regularly sized and regularly shaped tiles. Furthermore, one is forced to use a fine quantization (small tile size) that ensures the required transformation accuracy is achieved throughout the look up table, even though some parts of the look up table may require only coarse quantization. This means that these prior art look up tables consume more memory than would otherwise be required.
In order to reduce memory consumption while maintaining or even improving image transformation accuracy, a method and apparatus operative for transforming a description of a color from a first color space, defined by first color space parameters, into a second color space, defined by second color space parameters, has been developed. The method comprises the steps of storing transformation data in a search tree based database, receiving a set of first color space parameter values for transformation, generating a database index from the set of first color space parameter values, using the generated database index to access transformation data in the database, and transforming the first set of color space parameter values to a set of second color space parameter values based on the accessed transformation data.
In an exemplary embodiment the method comprises the steps of storing transformation data in a hashing table, receiving a set of first color space parameter values for transformation, generating a hashing key from the set of first color space parameter values, using the hashing key in a hashing function to generate a cell index, using the cell index to access transformation data in the hashing table and transforming the first set of color space parameter values to a set of second color space parameter values based on the accessed transformation data.
An image processor operative to transform a first image description, based in a first color space, described by a set of first color space parameters, into a second image description, based in a second color space, described by a set of second color space parameters comprises a database index generator and a search tree based database. The database index generator is operative to generate database indices based on sets of first color space parameter values. The search tree database is operative to store transformation information for a plurality of regions of color space, in association with the database indices.
In an exemplary embodiment of the image processor the database key generator further comprises a pixel processor operative to manipulate first color space parameter values to generate a key, and the cell index generator is operative to use the key to generate a cell index.
In one embodiment of the image processor the database comprises a hashing table.
One advantage of the present invention resides in a reduction in memory required to store color transformation look up tables at a specified level of accuracy.
Another advantage of the present invention is found in design flexibility afforded by the freedom to use rule based transformation processes, rather than being restricted to transformation by interpolation between look up table nodes.
Yet another advantage of the present invention is apparent in improved image transformations provided by a reduction in an amount of required design compromise. Since fine look up table tiling or quantization can be used where needed and any extra memory used by the fine tiling can be compensated for by using coarse tiling where coarse can be tolerated, fewer trade offs have to be made with regard to look up table quantization and required memory.
Still other advantages of the present invention will become apparent to those skilled in the art upon a reading and understanding of the detail description below.